package Ep03_HashTable._0001;

import java.util.HashMap;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/3/6 14:26
 * 说明： 力扣 0001 两数之和，高效的哈希表解法
 */

public class HashSolution {
    public static void main(String[] args) {
        // 两个3都会被put进哈希表，分别为(3,0)和(3,1)，后一个key为3的键值对会更新前一个3的键值对的value。所以结果为[1,2]
        int[] nums = {3,3,4};
        int target = 7;
        HashSolution m = new HashSolution();
        int[] res = m.twoSum(nums, target);
        for (int i = 0; i < 2; i++) {
            System.out.println(res[i]);
        }
    }

    public int[] twoSum(int[] nums, int target){
        // 由于不能和自己组成一个解，因此值应该唯一，所以放入哈希表中，nums[i]作为key，i作为value
        // 同时每次插入前都判断哈希表中是否存在 target-nums[i] 的 key 值
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(target-nums[i])){
                return new int[] {hashMap.get(target-nums[i]), i};
            }
            hashMap.put(nums[i], i);
        }
        return new int[0];
    }
}
